#pragma once

#include "LinkList.h"

template<typename T>
class LinkList<T*>
{
public:
	struct Node
	{
		Node():data(),next(nullptr){}

		Node(T* inData):data(inData),next(nullptr){}

		~Node(){delete data;};
		
		T* data;
		Node* next;
	};
	
	LinkList();
	~LinkList();
	
	int Size() const;

	/**
	 * 末端插入
	 * @param element 
	 */
	void Insert(T* element);
	
	T* Release(int index);
	
	// 搜索元素，返回元素节点
	Node* Find(const T* element, bool(*CompareFunc)(const T* a, const T* b));

	// 链表排序
	void Order(bool(*CompareFunc)(const T* a, const T* b));

	Node* GetHead()const {return head;}
private:
	int size;
	Node* head;
};

template <typename T>
LinkList<T*>::LinkList():
	size(0),
	head(nullptr)
{
}

template <typename T>
LinkList<T*>::~LinkList()
{
	Node* deletedNode = nullptr;
	Node* temp = head;
	while (temp)
	{
		deletedNode = temp;
		temp = temp->next;
		delete deletedNode;
	}
}

template <typename T>
int LinkList<T*>::Size() const
{
	return size;
}

template <typename T>
void LinkList<T*>::Insert(T* element)
{
	if (head)
	{
		// 如果 head 不为空

		Node* temp = head;
		// 如果 next 为空，说明temp是末端节点
		while (temp->next)
			temp = temp->next;

		temp->next = new Node(element);
	}
	else
	{
		// 如果 head 为空
		
		head = new Node(element);
	}

	++size;
}

template <typename T>
T* LinkList<T*>::Release(int index)
{
	// 前驱节点
	Node* prev = nullptr;
	// 当前遍历对象
	Node* temp = head;
	// 根据索引值，将前驱节点指针和当前节点指针进行偏移
	for (int i = 0; i < index; ++i)
	{
		prev = temp;
		temp = temp->next;
	}

	T* returnData = temp->data;
	if(prev)
	{
		temp->data = nullptr;
		prev = temp->next;
	}
	else
	{
		// 说明该节点是头结点
		temp->data = nullptr;
		head = temp->next;
	}
	delete temp;
	--size;
	
	return returnData;
}

template <typename T>
typename LinkList<T*>::Node* LinkList<T*>::Find(const T* element, bool(*CompareFunc)(const T* a, const T* b))
{
	Node* current = head;
	while(current)
	{
		if(CompareFunc(element, current->data))
			return current;

		current = current->next;
	}

	return nullptr;
}

template <typename T>
void LinkList<T*>::Order(bool(* CompareFunc)(const T* a, const T* b))
{
	if(!head)
		return;

	// 待排序节点
	Node* temp = head;
	head = nullptr;

	// 递增排序
	while(temp)
	{
		// 待排序节点中的下一个
		Node* next = temp->next;
		// 已排序节点迭代对象
		Node* iter = head;
		// 如果头结点为空，说明已排序链表为空，直接添加
		if(head == nullptr)
		{
			head = temp;
			head->next = nullptr;
		}
		else
		{
			// 当前节点的前驱节点
			Node* prev = nullptr;
			while(iter)
			{
				// 如果待排序节点小于等于当前迭代对象
				if(CompareFunc(temp->data, iter->data))
				{
					// 如果 当前已排序迭代对象前驱为空，说明当前节点是第一个
					if(prev == nullptr)
					{
						Node* tempNode = head;
						head = temp;
						head->next = tempNode;
					}
					else
					{
						// 否则，将待排序节点插入到迭代对象前面
						Node* tempNode = iter;
						prev->next = temp;
						prev->next->next = tempNode;
					}
					break;
				}
				else if(iter->next == nullptr)
				{
					temp->next = nullptr;
					iter->next = temp;
					break;
				}

				prev = iter;
				iter = iter->next;
			}
		}

		// 指向下一个待排序节点
		temp = next;
	}
}
